package com.zxy.leetcode._00000_00099._00050_00059;

/**
 * https://leetcode-cn.com/problems/jump-game/
 *
 * 跳跃游戏
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标。
 *
 * 标签：贪心
 */
public class Test00055 {

    public static void main(String[] args) {
        Test00055 test = new Test00055();

        int[] nums1 = {2,3,1,1,4};
        System.out.println(test.canJump(nums1));

        int[] nums2 = {3,2,1,0,4};
        System.out.println(test.canJump(nums2));

        int[] nums3 = {2, 0, 0};
        System.out.println(test.canJump(nums3));
    }

    /*
    每一步都跳到最远进行考虑
     */
    public boolean canJump(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }

        int curMost = nums[0];
        int maxIndex = nums.length-1;

        for (int i=1; i<=maxIndex; i++) {
            // 已经跳到了最后
            if (curMost >= maxIndex) {
                return true;
            }
            // 最远都跳不到这一步了，也没法往下跳了
            if (curMost < i) {
                return false;
            }
            // 当前为止能到的最远位置
            curMost = Math.max(curMost, nums[i] + i);
        }

        return curMost >= maxIndex;
    }

}
